package com.algrithom.sort;

import java.util.Arrays;

import com.util.CommonUtil;

/**
 * @author think
 * @version 1.0.0
 */
public class SelectSort {
    
    public static void main(String[] args){
        Integer[] array = new Integer[]{1,3,4,2,1,10,5};
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * 选择排序
     */
    private static void selectionSort(Integer[] array){
        int minPoint; // 存储最小元素的小标
        int len = array.length;
        int temp;
        int counter = 1;
        
        for (int i = 0; i < len - 1; i++) {
            minPoint = i;
            // 每完成一轮排序，就确定了一个相对最小元素，下一轮排序只对后面的元素排序
            for (int j = i + 1; j <= len - 1; j++) {
                // 如果待排数组中的某个元素比当前元素小，minPoint指向该元素的下标
                if (array[j] < array[minPoint]) {
                    minPoint = j;
                }
            }
            // 如果发现了更小的元素，交换位置
            if (minPoint != i) {
                temp = array[i];
                array[i] = array[minPoint];
                array[minPoint] = temp;
            }
            
            System.out.print("第" + counter + "轮排序结果：");
            CommonUtil.display(array);
            counter++;
        }
    }
    
    /**
     * 选择排序改进版
     *
     * @param array 数组
     */
    void selectionSort_improvement(Integer[] array){
        int minPoint;
        int maxPoint;
        int len = array.length;
        int temp;
        int counter = 1;
        
        for (int i = 0; i < len / 2; i++) {
            minPoint = i;
            maxPoint = i;
            // 每完成一轮排序，就确定了两个最值，下一轮排序时比较范围减少两个元素
            for (int j = i + 1; j <= len - 1 - i; j++) {
                // 如果待排数组中的某个元素比当前元素小，minPoint指向该元素的下标
                if (array[j] < array[minPoint]) {
                    minPoint = j;
                } else if (array[j] > array[maxPoint]) {
                    // 如果待排数组中的某个元素比当前元素大，maxPoint指向该元素的下标
                    maxPoint = j;
                }
            }
            // 如果发现了更小的元素，与第一个元素交换位置
            if (minPoint != i) {
                temp = array[i];
                array[i] = array[minPoint];
                array[minPoint] = temp;
                
                // 原来的第一个元素已经与下标为minPoint的元素交换了位置
                // 如果之前maxPoint指向的是第一个元素，那么需要将maxPoint重新指向array[minPoint]
                // 因为现在array[minPoint]存放的才是之前第一个元素中的数据
                if (maxPoint == i) {
                    maxPoint = minPoint;
                }
            }
            // 如果发现了更大的元素，与最后一个元素交换位置
            if (maxPoint != len - 1 - i) {
                temp = array[len - 1 - i];
                array[len - 1 - i] = array[maxPoint];
                array[maxPoint] = temp;
            }
            
            System.out.print("第" + counter + "轮排序结果：");
            CommonUtil.display(array);
            counter++;
        }
    }
}
